package com.example.question.dp.dp1;

public class Code06_5 {
    public static void main(String[] args) {
        Code06_5 code = new Code06_5();
        String s = code.longestPalindrome("aa");
        System.out.println(s);
    }

    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0 || s.length() == 1) {
            return s;
        }
        char[] chars = s.toCharArray();
        boolean[][] dp = new boolean[chars.length][chars.length];
        int startIndex = 1;
        int endIndex = 1;

        for (int col = 0; col < chars.length; col++) {
            for (int row = 0; row <= col; row++) {
                if (col == row) {
                    dp[row][col] = true;
                } else if (row + 1 == col) {
                    dp[row][col] = chars[row] == chars[col];
                } else {
                    dp[row][col] = chars[row] == chars[col] && dp[row + 1][col - 1];
                }

                if (dp[row][col] && ((col - row + 1) > (endIndex - startIndex + 1))) {
                    startIndex = row;
                    endIndex = col;
                }
            }
        }
        return s.substring(startIndex, endIndex + 1);
    }


}
